Number Theory

Euclid's Algorithm to find GCD of 2 numbers

def gcd(x,y):
    while(x!=y):
        if x>y:
            x=x-y
        else:
            y=y-x
    return x

Driver Code

Find the GCD of the following numbers

• 17 and 21 (Ans = 1)
• 16 and 20 (Ans = 4)
• 16 and 24 (Ans = 8)

if __name__=="__main__":
    print(gcd(17,21))
    print(gcd(16,20))
    print(gcd(16,24))

1
4
8

---

Extended Euclidean Algorithm to find multiplicative inverse of a number $a$ under mod $b$

def multiplicativeInverse(a,b):
    if gcd(a,b)>1:
        raise ArithmeticError("Parameters must be relatively prime")
    T1 = 0
    T2 = 1
    A = b
    N = a%b
    Q = int(A/N)
    R = A % N
    T = T1-T2*Q
    while R>0:
        A = N
        N = R
        T1 = T2
        T2 = T
        Q = int(A/N)
        R = A % N
        T = T1-T2*Q
    return (T2 if T2>0 else T2+b)

Driver Code

Find the multiplicative inverse of the following

• $3x = 1(\text{mod} \ 5)$ (Ans: $x = 2$)
• $11x = 1(\text{mod} \ 13)$ (Ans: $x = 6$)
• $11x = 1(\text{mod} \ 26)$ (Ans: $x = 19$)

if __name__=="__main__":
    p = multiplicativeInverse(3,5)
    q = multiplicativeInverse(11,13)
    r = multiplicativeInverse(11,26)
    print(p,(p*3)%5)
    print(q,(q*11)%13)
    print(r,(r*11)%26)

2 1
6 1
19 1

---

Chinese Remainder Theorem

def chineseRemainder(list_of_congruence):
    M = 1
    SUM = 0
    for i in list_of_congruence:
        M *= i[1]
    for i in list_of_congruence:
        M1 = int(M / i[1])
        M2 = multiplicativeInverse(M1,i[1])
        SUM += (i[0] * M1 * M2)
    return SUM % M

Driver Code

$X\equiv2($mod $3)$
$X\equiv3($mod $5)$
$X\equiv2($mod $7)$

Find the value of $X$ (Ans = 23)

if __name__=="__main__":
    congruence = [(2,3) , (3,5) , (2,7)]
    X = chineseRemainder(congruence)
    print(X)

23

We can check if our answer is correct

for i in congruence:
    p = X % i[1]
    q = i[0] % i[1]
    print(p == q)

True
True
True

You can check out these videos for more information

from IPython.display import YouTubeVideo as YTV

videos = ['yHwneN6zJmU','svBx8u5bMEg','lq285DDdmtw','zd1_iY0FSEo']

for video in videos:
    v = YTV(video, height = 370, width = 600)
    display(v)

---